struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;
	struct ListNode* head = NULL, * tail = NULL;
	head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
	while (list1 && list2)
	{
		if (list1->val < list2->val)
		{
			tail->next = list1;
			tail = tail->next;
			list1 = list1->next;
		}
		else
		{
			tail->next = list2;
			tail = tail->next;
			list2 = list2->next;

		}
	}
	if (list1)
		tail->next = list1;

	if (list2)
		tail->next = list2;

	struct ListNode* del = head;
	head = head->next;
	free(del);
	return head;
}